package _07_priority_queue.my_implements.heap;

import _00_my.exception.TechnicalLimitationException;
import _04_queue.AbstractQueue;
import _07_priority_queue.Priority;

import java.util.Iterator;

/**
 * @author: mornd
 * @dateTime: 2023/6/8 - 21:17
 * 大/小顶堆的定义
 */
public abstract class AbstractPriorityHeap<E extends Priority> extends AbstractQueue<E> {
    protected Priority[] data;
    protected int size;

    public AbstractPriorityHeap(int capacity) {
        data = new Priority[capacity];
    }

    /**
     * 求出下标 i 的父节点下标
     *
     * @param i -1 表示该节点没有分节点了
     * @return
     */
    protected int getParent(int i) {
        if (i > 0) {
            return (i - 1 >>> 1);
        }
        return -1;
    }

    /**
     * 1、入队新元素时，加入到数组的末尾（c）
     * 2、（上浮）不断比较c与它父节点（p）的优先级
     * - 如果p优先级低，则p向下移动，将p值赋给c，并找到下一个 p
     * - 直至p优先级更高 或者c的下标=0 为止
     *
     * @param e
     * @return
     */
    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }

        // 最后新元素插入的下标
        int c = size;
        // 父节点的下标
        int p;

        while (c > 0 && upwardComparison(data[p = getParent(c)], e)) {
            // 父节点向下移动
            data[c] = data[p];
            c = p;
        }

        data[c] = e;
        size++;
        return true;
    }

    /**
     * 向上比较规则
     *
     * @param son    子节点
     * @param parent 父节点
     * @return
     */
    protected abstract boolean upwardComparison(Priority son, Priority parent);

    /**
     * 向下比较规则
     *
     * @param parent 父节点
     * @param son    子节点
     * @return
     */
    protected abstract boolean downwardComparison(Priority parent, Priority son);

    @Override
    public E poll() {
        if (super.isEmpty()) {
            return null;
        }
        Priority e = data[0];
        size--;
        // 将尾部替换掉头部
        data[0] = data[size];

        // 下潜
        diving(0);

        data[size] = null;
        return (E) e;
    }

    protected void diving(int p) {
        int m = p;
        int l = 2 * p + 1;
        int r = l + 1;

//        if (l < size && data[l].priority() > data[m].priority()) {
        if (l < size && downwardComparison(data[m], data[l])) {
            m = l;
        }
        if (r < size && downwardComparison(data[m], data[r])) {
            m = r;
        }
        if (p != m) {
            swap(p, m);
            diving(m);
        }
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) data[0];
    }

    @Override
    public boolean isFull() {
        return size == data.length;
    }

    @Override
    public int size() {
        return size;
    }

    protected void swap(int i, int j) {
        Priority t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    @Override
    public Iterator<E> iterator() {
        throw new TechnicalLimitationException();
    }
}
